1. Field of the Invention
The invention relates generally to communications between master and slave devices and more particularly to systems and methods for implementing back-off timing in relation to retries of requests sent from a master device to a slave device.
2. Related Art
Modern high-performance computing systems may include multiple devices that perform the various of the computing system. For example, there may be multiple processors (which may act as masters, slaves, or both,) memories, input/output (I/O) devices, and the like. These different devices are typically connected to a bus so that they can communicate with each other, transfer data, and so on. Because there may be many devices that are trying to communicate using unlimited bandwidth of the bus, the communications between the devices should be as efficient as possible.
Transactions that are carried out between devices on the bus are typically executed in multiple steps or phases. For example, if a master device wishes to write data to a slave device, it is necessary in a typical system for the master to issue a write command, wait for acknowledgment from a target slave that the command can be accepted, and then transfer the write data to the bus to be sent to the target slave. There may be a number of these transactions that are being concurrently performed between the various devices on the bus, so it may be necessary to implement various mechanisms to prevent each transaction from interfering with the others.
One of the mechanisms that is commonly implemented to facilitate communications on a split-transaction bus as described above is a back-off mechanism for retries of commands that are not accepted by the target device on the first attempt. As mentioned above, a master device must wait for an acknowledgment from the target slave device in order to proceed with a transaction. If the slave device is not ready to accept the command when it is first transmitted from the master device (e.g., if the command buffer of the slave device is full,) the slave may send a RETRY response to the master. When the master device receives the RETRY response, it knows that the command has not been accepted, and may retry the command at a later time.
Because of the multi-phase nature of communications between the devices on the bus, there may be instances in which two different devices attempt to send commands to each other at approximately the same time. When each command is received by the respective target device, the target device may consider itself to be unavailable to accept the other device's command because of its own pending command and may therefore send a RETRY response to the other device. Each of the two devices must therefore retry sending its command at a later time. If both devices wait the same amount of time before sending their commands again, each of the devices will again be busy when the other device is command is received, and another retry will be necessary. This could be repeated indefinitely, with both devices stuck in an unending loop. This condition is referred to as “live lock.”
In order to avoid a live lock condition, it is common to implement a back-off timing mechanism. Typically, a back-off timing mechanism will cause a device to wait for increasing periods of time before retrying commands that have not been acknowledged. The back-off timing mechanism will also implement an element of randomness in the selection of the specific waiting period. The randomness in the selection of the waiting period reduces the chance that two devices will continue to interfere with each other. The increasing magnitude of the waiting period reduces the amount of resources that are spent in retrying the commands (since a device that is still busy after a short waiting period is likely to still be busy after another short waiting period.)
In order to implement a back-off timing mechanism, it is typically necessary to track of the number of retries of a command and the amount of time that remains before the command should be retried. In conventional systems, a set of registers is provided for each pending command. One of these registers stores of the number of retries corresponding to the command (a retry counter or indicator,) while another is used for a timer (a timer expiration value.) The first register is updated each time a retry response is received from the target slave device. The second register typically stores the time remaining before the command is to be retried, and consequently must be updated at each cycle. Because a typical system provides for a number of pending commands (e.g., eight or 16,) a corresponding number of retry indicators and timer values must also be provided. Conventional back-off timing mechanisms can therefore be expensive in terms of both the space that is required for them on the chip, and the processing that is required to update the timer values for each of the commands.
It would therefore be desirable to provide systems and methods for implementing back-off timing in retries of commands, where the systems and methods make more efficient use of both the space that is required on the chip and the processing resources that are required to track the timing of the retries.